package q235_lowestCommonAncestor;

import CommonClass.Common.TreeNode;
public class Solution {
    /*
    利用二叉搜索树的特点来找出两个节点的公共祖先节点
    相较于普通二叉树而言 当我们自上而下遍历时，找到第一个在p-q范围内的节点就是公共祖先
    所以只需要按照大小向左或者向右搜索即可
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }

        if (root.val <= Math.max(p.val, q.val) && root.val >= Math.min(p.val, q.val)) {
            return root;
        }

        if (root.val > Math.max(p.val, q.val)) {
            return lowestCommonAncestor(root.left, p, q);
        }

        if (root.val < Math.min(p.val, q.val)) {
            return lowestCommonAncestor(root.right, p, q);
        }
        // 也可以先判断是否大于最大值或者小于最小值
        // 否则就返回root 可以减少步骤
        return null;
    }
}
